﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace ProjectEulerSolutions
{
    /*
     * Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
n 	Relatively Prime 	φ(n) 	n/φ(n)
2 	1 	1 	2
3 	1,2 	2 	1.5
4 	1,3 	2 	2
5 	1,2,3,4 	4 	1.25
6 	1,5 	2 	3
7 	1,2,3,4,5,6 	6 	1.1666...
8 	1,3,5,7 	4 	2
9 	1,2,4,5,7,8 	6 	1.5
10 	1,3,7,9 	4 	2.5

It can be seen that n=6 produces a maximum n/φ(n) for n ≤ 10.

Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

     * */

    class Problem69 : IProblem
    {
        public string Calculate()
        {
            //brza verzija, sieve-like racunanje totienta, slican princip
            //
            //kao što je Euler primjetio,
            //za neka dva faktora m i n, ako je gcd(m,n) = 1, onda je phi(mn) = phi(m)*phi(n)
            //pošto je phi(p) = p - 1, za neki prosti broj p, to znači da svaki put kad nađemo faktor
            //phi umnožimo za (p-1) za taj broj
            //ono što je izgleda točno (iako sam više pogađao nego računao) je da ukoliko se koristi isti faktor
            //(primjerice 4 = 2*2), onda treba za prvi faktor pomnožiti sa (p-1), a za svaki naredni sa p

            //također ispada da je taj broj umnožak najmanjih prostih brojeva ispod milijun, što sam originalno i napravio
            //ali mi iz nekog razloga taj put odgovor nije priznalo :/

            int limit = 1000000;

            var q = CalculateTotients(limit);

            int best_n = 0;
            double best_ratio = 0;

            for (int i = 0; i < q.Length; i++)
            {
                double ratio = (i + 1) / (double) q[i];
                if (ratio > best_ratio)
                {
                    best_ratio = ratio;
                    best_n = i + 1;
                }
            }

            return best_n.ToString();
        }

        public int[] CalculateTotients(int limit)
        {
            SieveOfAtkin sieveOfAtkin = new SieveOfAtkin(limit);

            int[] totient = new int[limit];

            for (int i = 0; i < limit; i++)
                totient[i] = 1;


            for (int n = 2; n <= limit; n++)
            {
                if (sieveOfAtkin.IsPrime(n))
                {
                    int index = n - 1;
                    totient[index] *= n - 1;

                    index += n;

                    while (index < limit)
                    {
                        totient[index] *= n - 1;

                        int factorizedNumber = (index + 1) / n;

                        while (factorizedNumber % n == 0)
                        {
                            totient[index] *= n;
                            factorizedNumber /= n;
                        }

                        index += n;
                    }

                    continue;
                }

                double ratio = n / (double)totient[n - 1];
            }

            return totient;
        }
    }
}
